import collections


class Solution(object):
    def leadsToDestination(self, n, edges, source, destination):
        """
        :type n: int
        :type edges: List[List[int]]
        :type source: int
        :type destination: int
        :rtype: bool
        """
        edge = collections.defaultdict(set)
        d = collections.defaultdict(int)
        for item in edges:
            if item[1] not in edge[item[0]]:
                d[item[1]] += 1
                if item[0] not in d:
                    d[item[0]] = 0
                edge[item[0]].add(item[1])
        now_set = set()
        for item in d:
            if d[item] == 0 and item != source:
                now_set.add(item)
        while now_set:
            next_set = set()
            for item in now_set:
                for next_node in edge[item]:
                    d[next_node] -= 1
                    if d[next_node] == 0 and next_node != source:
                        next_set.add(next_node)
            now_set = next_set
        now_set = {source}
        path_node = set()
        while now_set:
            next_set = set()
            for item in now_set:
                if edge[item]:
                    for next_node in edge[item]:
                        path_node.add(next_node)
                        d[next_node] -= 1
                        if d[next_node] == 0:
                            next_set.add(next_node)
                else:
                    if item != destination:
                        return False
            now_set = next_set
        for node in path_node:
            if d[node] != 0:
                return False
        return True


data = Solution()
n = 4
edges = [[0, 1], [0, 2], [1, 3], [2, 3]]
source = 0
destination = 3
print(data.leadsToDestination(n, edges, source, destination))
n = 4
edges = [[0, 1], [0, 3], [1, 2], [2, 1]]
source = 0
destination = 3
print(data.leadsToDestination(n, edges, source, destination))
n = 3
edges = [[0, 1], [1, 2]]
source = 0
destination = 2
print(data.leadsToDestination(n, edges, source, destination))
n = 5
edges = [[0, 3], [1, 2], [2, 1], [3, 4]]
source = 0
destination = 3
print(data.leadsToDestination(n, edges, source, destination))
n = 5
edges = [[0,1],[0,2],[0,3],[0,3],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
source = 0
destination = 4
print(data.leadsToDestination(n, edges, source, destination))
